package leetcode.other.greedy;

import java.util.Arrays;

/**
 * @Description:
 * 北美洲东南部，有一片神秘的海域，是海盗最活跃的加勒比海，有一天，海盗们截获了一搜装满各种各样的古董货船
 * 每一件古董都价值连城，一旦打碎就失去了它的价值，而每一艘货船的载重量都是有限的，所以他们必须在不超载的前提下，
 * 选择一些古董来装船，使得这些古董的总价值最大。
 * 海盗船的载重量为W，每件古董的重量为w[i]，海盗们该如何选择装载哪些古董？
 * 比如 W 为 30，w = {3, 5, 4, 10, 7, 14, 2, 11}，则选择 {3, 5, 4, 10, 7} 总价值最大，为 29
 * @Author Ammar
 * @Create 2023/7/2 22:01
 */
public class 海盗问题 {

    public static void main(String[] args) {
        // 贪心策略，每一次都优先选择重量最小的古董
        int capacity = 30;
        int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};
        int count = 0, weight = 0;
        Arrays.sort(weights);

        for (int i = 0; i < weights.length && weight < capacity; i++) {
            int newWeight = weight + weights[i];
            if (newWeight <= capacity) {
                weight = newWeight;
                count++;
            }
        }
        System.out.println("count = " + count);
    }
}
